#include <stddef.h>
#include <stdint.h>
#include <stdio.h>

#define NULL_PTR ((void *)0)
#ifndef TRUE
#define TRUE (1u)
#endif
#ifndef FALSE
#define FALSE (0u)
#endif

typedef unsigned char uint8;
typedef unsigned int uint32;
typedef unsigned char boolean;
typedef unsigned long long size;

#define MEMORY_POOL_SIZE 1024 // 内存池大小
#define ENABLE_MAIN (1) // Enable main function example

typedef struct memory_block
{
  size size;
  struct memory_block *next;
} memory_block_t;

static uint8 memory_pool[MEMORY_POOL_SIZE]; // Memory pool
static memory_block_t *free_list;           // The header pointer of the idle list

void memory_init(void)
{
  free_list = (memory_block_t *)memory_pool;
  free_list->size = MEMORY_POOL_SIZE - sizeof(memory_block_t);
  free_list->next = NULL;
}

void *memory_malloc(size size)
{
  memory_block_t *prev = NULL;
  memory_block_t *current = free_list;

  while (current != NULL)
  {
    if (current->size >= size)
    {
      if (current->size >= size + sizeof(memory_block_t))
      {
        memory_block_t *next_block = (memory_block_t *)((uint8 *)current + sizeof(memory_block_t) + size);
        next_block->size = current->size - size - sizeof(memory_block_t);
        next_block->next = current->next;

        if (prev == NULL)
        {
          free_list = next_block;
        }
        else
        {
          prev->next = next_block;
        }
      }
      else
      {
        if (prev == NULL)
        {
          free_list = current->next;
        }
        else
        {
          prev->next = current->next;
        }
      }

      current->size = size;
      return (void *)((uint8 *)current + sizeof(memory_block_t));
    }

    prev = current;
    current = current->next;
  }

  return NULL;
}

void memory_free(void *ptr)
{
  if (ptr == NULL)
  {
    return;
  }

  memory_block_t *block = (memory_block_t *)((uint8 *)ptr - sizeof(memory_block_t));
  memory_block_t *current = free_list;
  memory_block_t *prev = NULL;

  while (current != NULL && current < block)
  {
    prev = current;
    current = current->next;
  }

  if (prev == NULL)
  {
    free_list = block;
    block->next = current;
  }
  else
  {
    prev->next = block;
    block->next = current;
  }

  // Merge adjacent free blocks
  if ((uint8 *)block + sizeof(memory_block_t) + block->size == (uint8 *)block->next)
  {
    block->size += sizeof(memory_block_t) + block->next->size;
    block->next = block->next->next;
  }

  if (prev != NULL && (uint8 *)prev + sizeof(memory_block_t) + prev->size == (uint8 *)block)
  {
    prev->size += sizeof(memory_block_t) + block->size;
    prev->next = block->next;
  }
}

#if ENABLE_MAIN
int main(void)
{
  memory_init();

  void *ptr1 = memory_malloc(100);
  printf("Allocated 100 bytes at %p\n", ptr1);

  void *ptr2 = memory_malloc(200);
  printf("Allocated 200 bytes at %p\n", ptr2);

  memory_free(ptr1);
  printf("Freed 100 bytes from %p\n", ptr1);

  void *ptr3 = memory_malloc(50);
  printf("Allocated 50 bytes at %p\n", ptr3);

  memory_free(ptr2);
  printf("Freed 200 bytes from %p\n", ptr2);

  memory_free(ptr3);
  printf("Freed 50 bytes from %p\n", ptr3);

  return 0;
}
#endif
